package com.leetcode.graph;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/9/17 11:03
 */
public class NetworkDelayTime_743 {

    // 建议做之前先看B站UP正月点灯笼的讲解视频 https://www.bilibili.com/video/BV1ts41157Sy
    // 迪杰斯特拉算法的典例
    public int networkDelayTime(int[][] times, int N, int K) {
        // 邻接表，int[]中存储了点和权值
        Map<Integer, List<int[]>> map = new HashMap<>();
        int[] dis = new int[N + 1];
        // 如果走完所有点，那么不会有Integer.MAX_VALUE，否则就是没走完
        Arrays.fill(dis, Integer.MAX_VALUE);
        boolean[] visited = new boolean[N + 1];
        for (int[] t : times) {
            // 构建邻接表
            map.computeIfAbsent(t[0], integer -> new ArrayList<>()).add(new int[]{t[1], t[2]});
        }
        // 将起点和冗余点的距离设为0
        dis[K] = 0;
        dis[0] = 0;
        // 建立优先队列，长度大的会自动排到后面
        Queue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(o -> dis[o]));
        queue.offer(K);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (visited[node]) continue;
            visited[node] = true;
            List<int[]> list = map.getOrDefault(node, Collections.emptyList());
            for (int[] arr : list) {
                int next = arr[0];
                if (visited[next]) continue;
                // 如果长度较长，那么会自动移到后面
                // 贪心思想。如果d[1] > d[2]，那么不可能会有0 -> 2 -> 1的距离大于0 -> 1的距离
                // 所以可以直接在满足条件的基础上入队
                dis[next] = Math.min(dis[next], dis[node] + arr[1]);
                queue.offer(next);
            }
        }
        int max = Arrays.stream(dis).max().getAsInt();
        return max == Integer.MAX_VALUE ? -1 : max;
    }

}
